# ---
# title: 1175. Prime Arrangements
# id: problem1175
# author: Tian Jun
# date: 2020-10-31
# difficulty: Easy
# categories: Math
# link: <https://leetcode.com/problems/prime-arrangements/description/>
# hidden: true
# ---
# 
# Return the number of permutations of 1 to `n` so that prime numbers are at
# prime indices (1-indexed.)
# 
# _(Recall that an integer  is prime if and only if it is greater than 1, and
# cannot be written as a product of two positive integers both smaller than
# it.)_
# 
# Since the answer may be large, return the answer **modulo`10^9 + 7`**.
# 
# 
# 
# **Example 1:**
# 
#     
#     
#     Input: n = 5
#     Output: 12
#     Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.
#     
# 
# **Example 2:**
# 
#     
#     
#     Input: n = 100
#     Output: 682289015
#     
# 
# 
# 
# **Constraints:**
# 
#   * `1 <= n <= 100`
# 
# 
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end
